DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2024.4

Max Weight Independent Set in Sparse Graphs with No Long Claws

Authors: Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract

We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.

Cite as

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski. Max Weight Independent Set in Sparse Graphs with No Long Claws. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrishami_et_al:LIPIcs.STACS.2024.4,
  author =	{Abrishami, Tara and Chudnovsky, Maria and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Max Weight Independent Set in Sparse Graphs with No Long Claws}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.4},
  URN =		{urn:nbn:de:0030-drops-197148},
  doi =		{10.4230/LIPIcs.STACS.2024.4},
  annote =	{Keywords: Max Weight Independent Set, subdivided claw, hereditary classes}
}

Search Results

Documents authored by Abrishami, Tara

Max Weight Independent Set in Sparse Graphs with No Long Claws

Abstract

Cite as

Thanks for your feedback!

Could not send message